package leetcode.f1t100;

/**
 * log(n)寻找升序不唯一数组中某个值出现的范围
 * https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 *
 * @Author lichongxiao
 * @Date 2022/10/9 11:20
 */
public class Q34_FindRangeOfElementInSortedArray {

    /**
     * 待优化，两个二分查找，控制好边界
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[]{-1, -1};
        int length = nums.length, left = 0, right = length - 1;
        if (length== 0 || nums[0] > target || nums[length - 1] < target) {
            return ans;
        }
        int middle = 0;
        while (left <= right) {
            middle = (left + right) / 2;
            if (nums[middle] == target) {
                ans[0] = middle;
                ans[1] = middle;
                if (ans[0] != 0) {
                    left = 0;
                    right = ans[0];
                    while (left < right) {
                        middle = (left + right) / 2;
                        if (nums[middle] == target) {
                            right = middle;
                        } else {
                            left = middle + 1;
                        }
                    }
                    ans[0] = left;
                }
                if (ans[1] != length - 1) {
                    left = ans[1];
                    right = length - 1;
                    while (left < right) {
                        middle = (left + right) / 2 + 1;
                        if (nums[middle] == target) {
                            left = middle;
                        } else {
                            right = middle - 1;
                        }
                    }
                    ans[1] = right;
                }
                return ans;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2,2};
        int[] ans = new Q34_FindRangeOfElementInSortedArray().searchRange(nums, 2);
        System.out.println(ans[0] + "_" + ans[1]);
    }
}
